package com.wxweven.algorithm.array.twopointer;

class LC845最长山脉 {

    /*
     * 我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
     *
     * B.length >= 3
     * 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
     * （注意：B 可以是 A 的任意子数组，包括整个数组 A。）
     *
     * 给出一个整数数组 A，返回最长 “山脉” 的长度。
     *
     * 如果不含有 “山脉” 则返回 0。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：[2,1,4,7,3,2,5]
     * 输出：5
     * 解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
     * 示例 2：
     *
     * 输入：[2,2,2]
     * 输出：0
     * 解释：不含 “山脉”。
     *
     * 简单说就是 先递增然后再递减 的连续子序列的最大长度
     *
     * 视频讲解：https://www.youtube.com/watch?v=2cUhalOGJB8
     */
    public int longestMountain(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }

        int len = arr.length;
        // 左侧山脚
        int left = 0;
        // 右侧山脚
        int right = 0;

        int res = 0;

        // 最少得三个数才能构成 山
        while (left + 2 < len) {
            right = left + 1;

            if (arr[left] < arr[right]) {
                // 右边的数比当前数大，说明当前数可以作为左侧山脚

                // 让right一直往右，继续找比当前大的数，直到找到山顶：下一个元素比当前元素小的数为山顶；
                // 确保数组不越界：right+1<len
                while (right + 1 < len && arr[right] < arr[right + 1]) {
                    right++;
                }

                // 找到山顶后(right就是山顶)，如果下一个元素比当前小，那就是真的山顶
                // 确保数组不越界：right+1<len
                if (right + 1 < len && arr[right] > arr[right + 1]) {

                    // 让right一直往右，继续找比当前小的数，直到找到右侧山脚
                    while (right + 1 < len && arr[right] > arr[right + 1]) {
                        right++;
                    }

                    // 计算最长山脉
                    res = Math.max(res, right - left + 1);
                } else {
                    // 如果第一个while到达山顶后，下一个数等于山顶，那说明这一轮没有找到山脉，left从right下一个开始找
                    right++;
                }
            }

            left = right;
        }

        return res;
    }
}